#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/9 16:54
# @USER    : Shengji He
# @File    : SubstringConcatenationAllWords.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from collections import Counter
from typing import List


def combinations(items, n):
    """ 取得n个不同的项， 顺序是有意义的"""

    def skipIthItem(items, i):
        return items[:i] + items[i + 1:]

    return _combinators(skipIthItem, items, n)


def uniqueCombinations(items, n):
    """取得n个不同的项，顺序无关"""

    def afterIthItem(items, i):
        return items[i + 1:]

    return _combinators(afterIthItem, items, n)


def _combinators(_handle, items, n):
    """ 抽取下列组合的通用结构"""
    if n == 0:
        yield []
    for i, item in enumerate(items):
        this_one = [item]
        for cc in _combinators(_handle, _handle(items, i), n - 1):
            yield this_one + cc


class Solution:
    def __init__(self):
        self.marked = {}

    def findIndex(self, targetStr, s):
        ls = 0
        while s[ls:].count(targetStr) > 0:
            idx = s[ls:].index(targetStr)
            self.marked[idx + ls] = targetStr
            ls = idx + 1 + ls

    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        """
        You are given a string, s, and a list of words, words, that are all of the same length. Find all starting
        indices of substring(s) in s that is a concatenation of each word in words exactly once
        and without any intervening characters.

        Example 1:

        Input:
          s = "barfoothefoobarman",

          words = ["foo","bar"]

        Output: [0,9]

        Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.

        The output order does not matter, returning [9,0] is fine too.

        Example 2:

        Input:
          s = "wordgoodgoodgoodbestword",
          words = ["word","good","best","word"]

        Output: []

        :param s: str
        :param words: List[str]
        :return: List[int]
        """
        # ans = []
        # if len(s) == 0 or len(words)==0 or len(''.join(words)) > len(s):
        #     return ans
        # founded = []
        # for element in words:
        #     if element not in founded:
        #         self.findIndex(element, s)
        #         if element not in self.marked.values():
        #             return ans
        #         founded.append(element)
        # indexs = sorted(self.marked)
        # ls = 0
        # while ls < len(indexs) - len(words) + 1:
        #     idx = indexs[ls]
        #     wc = words.copy()
        #     wc.remove(self.marked[idx])
        #     length = len(wc)
        #     while length:
        #         next_idx = idx + len(self.marked[idx])
        #         if next_idx in indexs and self.marked[next_idx] in wc:
        #             idx = next_idx
        #             wc.remove(self.marked[idx])
        #             length = len(wc)
        #         else:
        #             break
        #     if length == 0:
        #         ans.append(indexs[ls])
        #     ls += 1
        # return ans

        # way 2
        # if not s or not words:
        #     return []
        # one_word = len(words[0])
        # all_len = len(words) * one_word
        # n = len(s)
        # words = Counter(words)
        # res = []
        # for i in range(0, n - all_len + 1):
        #     tmp = s[i:i + all_len]
        #     c_tmp = []
        #     for j in range(0, all_len, one_word):
        #         c_tmp.append(tmp[j:j + one_word])
        #     if Counter(c_tmp) == words:
        #         res.append(i)
        # return res
        if not s or not words:
            return []
        one_word = len(words[0])
        word_num = len(words)
        n = len(s)
        if n < one_word:
            return []
        words = Counter(words)
        res = []
        for i in range(0, one_word):
            cur_cnt = 0
            left = i
            right = i
            cur_Counter = Counter()
            while right + one_word <= n:
                w = s[right:right + one_word]
                right += one_word
                if w not in words:
                    left = right
                    cur_Counter.clear()
                    cur_cnt = 0
                else:
                    cur_Counter[w] += 1
                    cur_cnt += 1
                    while cur_Counter[w] > words[w]:
                        left_w = s[left:left + one_word]
                        left += one_word
                        cur_Counter[left_w] -= 1
                        cur_cnt -= 1
                    if cur_cnt == word_num:
                        res.append(left)
        return res


if __name__ == '__main__':
    S = Solution()
    # s = "aaaaaaaa"
    # words = ["aa","aa","aa"]
    # s = "wordgoodgoodgoodbestword"
    # words = ["word","good","best","word"]
    s = "barfoothefoobarfooman"
    words = ["foo", "bar"]
    # s = "pjzkrkevzztxductzzxmxsvwjkxpvukmfjywwetvfnujhweiybwvvsrfequzkhossmootkmyxgjgfordrpapjuunmqnxxdrqrfgkrsjqbs" \
    #     "zgiqlcfnrpjlcwdrvbumtotzylshdvccdmsqoadfrpsvnwpizlwszrtyclhgilklydbmfhuywotjmktnwrfvizvnmfvvqfiokkdprznnnj" \
    #     "ycttprkxpuykhmpchiksyucbmtabiqkisgbhxngmhezrrqvayfsxauampdpxtafniiwfvdufhtwajrbkxtjzqjnfocdhekumttuqwovfjr" \
    #     "gulhekcpjszyynadxhnttgmnxkduqmmyhzfnjhducesctufqbumxbamalqudeibljgbspeotkgvddcwgxidaiqcvgwykhbysjzlzfbupkq" \
    #     "unuqtraxrlptivshhbihtsigtpipguhbhctcvubnhqipncyxfjebdnjyetnlnvmuxhzsdahkrscewabejifmxombiamxvauuitoltyymsa" \
    #     "rqcuuoezcbqpdaprxmsrickwpgwpsoplhugbikbkotzrtqkscekkgwjycfnvwfgdzogjzjvpcvixnsqsxacfwndzvrwrycwxrcismdhqap" \
    #     "oojegggkocyrdtkzmiekhxoppctytvphjynrhtcvxcobxbcjjivtfjiwmduhzjokkbctweqtigwfhzorjlkpuuliaipbtfldinyetoybvu" \
    #     "gevwvhhhweejogrghllsouipabfafcxnhukcbtmxzshoyyufjhzadhrelweszbfgwpkzlwxkogyogutscvuhcllphshivnoteztpxsaoaa" \
    #     "cgxyaztuixhunrowzljqfqrahosheukhahhbiaxqzfmmwcjxountkevsvpbzjnilwpoermxrtlfroqoclexxisrdhvfsindffslyekrzwz" \
    #     "qkpeocilatftymodgztjgybtyheqgcpwogdcjlnlesefgvimwbxcbzvaibspdjnrpqtyeilkcspknyylbwndvkffmzuriilxagyerjptbg" \
    #     "eqgebiaqnvdubrtxibhvakcyotkfonmseszhczapxdlauexehhaireihxsplgdgmxfvaevrbadbwjbdrkfbbjjkgcztkcbwagtcnrtqryu" \
    #     "qixtzhaakjlurnumzyovawrcjiwabuwretmdamfkxrgqgcdgbrdbnugzecbgyxxdqmisaqcyjkqrntxqmdrczxbebemcblftxplafnyoxq" \
    #     "imkhcykwamvdsxjezkpgdpvopddptdfbprjustquhlazkjfluxrzopqdstulybnqvyknrchbphcarknnhhovweaqawdyxsqsqahkepluyp" \
    #     "wrzjegqtdoxfgzdkydeoxvrfhxusrujnmjzqrrlxglcmkiykldbiasnhrjbjekystzilrwkzhontwmehrfsrzfaqrbbxncphbzuuxetesh" \
    #     "yrveamjsfiaharkcqxefghgceeixkdgkuboupxnwhnfigpkwnqdvzlydpidcljmflbccarbiegsmweklwngvygbqpescpeichmfidgsjmk" \
    #     "vkofvkuehsmkkbocgejoiqcnafvuokelwuqsgkyoekaroptuvekfvmtxtqshcwsztkrzwrpabqrrhnlerxjojemcxel "
    # words = ["dhvf", "sind", "ffsl", "yekr", "zwzq", "kpeo", "cila", "tfty", "modg", "ztjg", "ybty", "heqg", "cpwo",
    #          "gdcj", "lnle", "sefg", "vimw", "bxcb"]
    print(S.findSubstring(s, words))
    print('done')
